package junior.回溯法.四阶幻方;

public class 优化_暴力回溯求解_进阶 {
    static int N = 4;  // 4阶幻方：基本形式880个，翻转旋转将会有7040（大概1500ms，即：1.5秒）
    static int[] stack = new int[100];
    static int[] visit = new int[100];  // 0:未标记，1：标记
    static int top = 0;
    static int total1 = 0; // 解的个数
    public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
        fun1(0);
        long t2 = System.currentTimeMillis();
        System.out.println("求解的时间："+(t2-t1)+" ms\t"+(t2-t1)/1000+" s");
        System.out.println("解的个数："+total1);
    }

    public static void fun1(int n){ // 0-15 的 n 个位置
        if(n == N*N){
            show(stack,N);
            total1++;
            return;
        }
        for (int i = 1; i <= N*N; i++) {  // C (n,r) n个里面取r个元素，进行组合
            if(visit[i] == 0){
                boolean i_isOk = true;
                if((n+1) % 4 == 0){
                    System.out.println(666);
                    if(stack[n] + stack[n-1] + stack[n-2] + i != 34){
                        i_isOk = false;
                    }
                }
                if(n/4 >= 3){
                    System.out.println(777);
                    if(stack[n-12] + stack[n-8] + stack[n-4] + i != 34){
                        i_isOk = false;
                    }
                }
                if(i_isOk){
                    System.out.println("i = " + i);
                    stack[top++] = i;
                    visit[i] = 1;  // 1 已使用
                    fun1(n+1);
                    visit[i] = 0;  // 0 未使用
                    top--;
                }
            }

        }
    }
    public static void show(int[] check,int N) { // N:阶数

        System.out.println(stack[0]+"\t"+stack[1]+"\t"+stack[2]+"\t"+stack[3]);
        System.out.println(stack[4]+"\t"+stack[9]+"\t"+stack[7]+"\t"+stack[10]);
        System.out.println(stack[5]+"\t"+stack[8]+"\t"+stack[11]+"\t"+stack[12]);
        System.out.println(stack[6]+"\t"+stack[13]+"\t"+stack[14]+"\t"+stack[15]);
        System.out.println();

    }
}

